Search results for "parametrizēti algoritmi"

Parametrizētu algoritmu paātrinājumi kvantu datoram

2021

Darbā tiek aplūkots, kā uz kvantu datora iespējams paātrināt zināmus parametrizētus algoritmus problēmām “Closest string”, “Cluster vertex deletion”, “Cluster editing”, “Vertex cover” un “Longest path” problēmu risinājumiem, ka arī to uzlabošana kvantu datoram, izmantojot kvantu algoritmus meklēšanas koka apstaigāšanai un dinamiskai programmēšanai. Ir parādīts, kā izveidot kvantu algoritmus “Cluster vertex deletion” problēmas risinājumam ar laika sarežģītību 𝑂(1.7321^𝑘 * √𝑘 * 𝑛^3) un “Vertex cover” problēmai ar laiku 𝑂(1.175^𝑘 * 𝑘^𝑂(1) + 𝑛√𝑚), kas ir labāk, nekā labākajiem zināmajiem algoritmiem ar laiku 𝑂(1.9102^𝑘 * (𝑛 + 𝑚)) un 𝑂(1.2738^𝑘 + 𝑘𝑛), attiecīgi. Ka arī ir parād…